package algorithms.question.class17;

import common.util.MyUtil;

/**
 * https://leetcode-cn.com/problems/distinct-subsequences-ii/
 * <p>
 * 给定一个字符串Str
 * 返回Str的所有子序列中有多少不同的字面值
 *
 * @author guichang
 * @date 2021/8/16
 */

@SuppressWarnings("all")
public class Code5_子序列不同的字面值 {

    public static void main(String[] args) {
        String str = "lee";
        MyUtil.print(distinctSubseqII(str));
    }

    public static int distinctSubseqII(String str) {
        if (str == null || str.length() == 0) {
            return 0;
        }
        char[] strs = str.toCharArray();
        int[] pre = new int[26];
        int res = 1; // 初始一个空集合
        for (int i = 0; i < strs.length; i++) {
            // 新加入的
            int newAdd = res;
            // 当前字符的坐标
            int preIndex = strs[i] - 'a';
            // 总和为 之前的 + 新加入的 - 上一个以当前字符结尾的
            res = res + newAdd - pre[preIndex];
            // 设置当前字符结尾的数量
            pre[preIndex] = newAdd;
        }
        return res - 1; // 最后减一个空集合
    }

}